package arithmetic1.tree.binaryTree;

/*
    线索化二叉树
 */
public class ThreadBinaryTree {
    //根节点
    private Node root;
    //当前节点的前驱节点指针
    private Node pre;

    public ThreadBinaryTree(Node root) {
        this.root = root;
    }

    //将二叉树中序线索化
    public void infixThread(Node root){
        if(root!=null){
            //线索化左子树
            infixThread(root.left);
            //线索化当前节点
            if(root.left==null){    //当前节点左子节点为空才需要线索化
                root.left=pre;
                root.leftFlag=true;
            }
            if(pre!=null && pre.right==null){   //处理该节点的后继节点
                pre.right=root;
                pre.rightFlag=true;
            }
            //处理一个节点后将pre指向该节点
            pre=root;
            //线索化右子树
            infixThread(root.right);
        }
    }
    public void infixThread(){
        infixThread(root);
    }

    //中序遍历线索化二叉树(递归方式)
    public void infixOrder1(Node root){
        if(root!=null){
            //向左遍历,左指针不为空并且左指针的类型是指向子节点
            if(root.left!=null && root.leftFlag==false){
                infixOrder1(root.left);
            }
            //遍历该节点
            System.out.print(root.data+"\t");
            //向右遍历,右指针不为空，并且右指针类型为指向子节点
            if(root.right!=null && root.rightFlag==false){
                infixOrder1(root.right);
            }
        }
    }
    public void infixOrder1(){
        infixOrder1(root);
    }

    //中序遍历线索化二叉树(非递归方式)
    public void infixOrder2(){
        //定义一个辅助指针
        Node node=root;
        while (node!=null){
            //找到中序遍历的每一个线索化的节点
            while (node.leftFlag==false){
                node=node.left;
            }
            //输出当前节点
            System.out.print(node.data+"\t");
            //如果该节点的右指针类型为指向后继节点，就将node指向该后继节点，并且打印后继节点
            while (node.rightFlag==true){
                node=node.right;
                System.out.print(node.data+"\t");
            }
            node=node.right;
        }
    }

}

class Node{
     int data;
     Node left;
     Node right;
     //为false代表指向的是左子节点，为true代表指向的是前驱节点
     boolean leftFlag;
    //为false代表指向的是右子节点，为true代表指向的是后继节点
     boolean rightFlag;

    public Node(int data) {
        this.data = data;
        leftFlag=false;
        rightFlag=false;
    }
}

class Test1{
    public static void main(String[] args) {
        Node node1=new Node(1);
        ThreadBinaryTree tree=new ThreadBinaryTree(node1);
        Node node2=new Node(2);
        Node node3=new Node(3);
        Node node4=new Node(4);
        Node node5=new Node(5);
        Node node6=new Node(6);
        Node node7=new Node(7);

        node1.left=node2;
        node1.right=node3;
        node2.left=node4;
        node2.right=node5;
        node3.left=node6;
        node3.right=node7;

        //中序线索化二叉树
        tree.infixThread();
//        Node node=node4.right;
//        System.out.println(node.data);

        //中序遍历二叉树
        tree.infixOrder1();
        System.out.println();
        tree.infixOrder2();
    }
}
